`
https://leetcode.cn/problems/minimum-falling-path-sum/
`

/**
 * @param {number[][]} matrix
 * @return {number}
 */
var minFallingPathSum = function (matrix) {
  const n = matrix.length

  // 定义：dp[i][j] 表示从第一行任意位置向下落，落到dp[i][j] 位置的下降路径最小和
  const dp = Array.from({ length: n }, () => new Array(n).fill(0))
  // 第一层肯定是原本的值
  for (let i = 0; i < n; i++) {
    dp[0][i] = matrix[0][i]
  }

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < n; j++) {
      // 上一层可能落到当前位置的数组
      const maybe = []
      // 左上的值
      if (j - 1 >= 0) maybe.push(dp[i - 1][j - 1])
      // 正上的值
      maybe.push(dp[i - 1][j])
      // 右上的值
      if (j + 1 < n) maybe.push(dp[i - 1][j + 1])
      // 取可能落到当前位置的值的最小值，加上这个位置原本的值
      dp[i][j] = matrix[i][j] + Math.min(...maybe)
    }
  }

  // 答案可能出现在最后一列的任意位置，返回最后一列的最小值
  return Math.min(...dp[n - 1])
};